package com.zjsru.oneDay202205;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/6/11
 *
 * 将字符串翻转到单调递增
 * 输入：s = "00110"
 * 输出：1
 * 解释：翻转最后一位得到 00111.
 *
 * 输入：s = "010110"
 * 输出：2
 * 解释：翻转得到 011111，或者是 000111。
 */
public class minFlipsMonoIncr {
    public int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, ans = 0;
        int[] g = new int[n + 10];
        Arrays.fill(g, n + 10);
        for (int i = 0; i < n; i++) {
            int t = s.charAt(i) - '0';
            int l = 1, r = i + 1;
            while(l < r){
                int mid = l + r >> 1;
                if(g[mid] > t) r =mid;
                else l = mid + 1;
            }
            g[r] = t;
            ans = Math.max(ans,r);
        }
        return n - ans;
    }
    
    public static void main(String[] args) {
        minFlipsMonoIncr minFlipsMonoIncr = new minFlipsMonoIncr();
        String s = "00110";
        System.out.println(minFlipsMonoIncr.minFlipsMonoIncr(s));
    }
}
